

后端从IR创建机器指令是一项非常重要的任务。实现它的一种常见方法是利用DAG:

\begin{enumerate}
\item
首先，必须从IR创建DAG。DAG的一个节点表示一个操作，边缘表示控制和数据流依赖关系。

\item
接下来，必须遍历DAG并使类型和操作合法化，只使用硬件支持的类型和操作。这要求我们创建一个配置，告诉框架如何处理非合法类型和操作。例如，一个64位值可以拆分为两个32位值，两个64位值的乘法可以更改为库调用，计数填充等复杂操作可以扩展为计算该值的一系列更简单的操作。

\item
然后，利用模式匹配对DAG中的节点进行匹配，并用机器指令替换节点。我们在前一章中看到了这种模式。

\item
最后，指令调度程序将机器指令重新排序为更高效的顺序。
\end{enumerate}

通过选择DAG对指令选择过程的高级描述若对更多细节感兴趣，可以在\url{https://llvm.org/docs/CodeGenerator.html#selectiondaginstruction-selection-process}的LLVM目标无关代码生成器用户指南中找到。

此外，LLVM中的所有后端都实现了选择DAG，其主要优点是可以生成高性能的代码，但这是有代价的:创建DAG很昂贵，并且减慢了编译速度此，所以这促使LLVM开发人员寻找其他更理想的方法。一些目标通过FastISel实现指令选择，这只用于未优化的代码。可以快速生成代码，但生成的代码不如选择DAG方法生成的代码。还增加了一种全新的指令选择方法，使测试工作量增加了一倍。指令选择还使用另一种方法，称为全局指令选择，我们将在稍后的全局指令选择一节中对其进行研究。

本章中，目标是实现足够的后端，来实现一个简单的IR功能:

\begin{cpp}
define i32 @f1(i32 %a, i32 %b) {
    %res = and i32 %a, %b
    ret i32 %res
}
\end{cpp}

此外，对于一个真正的后端，需要更多的代码，必须添加什么来实现更大的功能。

为了通过选择DAG实现指令选择，需要创建两个新类:M88kISelLowering和M88kDAGToDAGISel。前一个类用于定制DAG，例如：通过定义哪些类型是合法的，包含支持降低函数和函数调用的代码。后一个类执行DAG转换，实现主要是从目标描述生成的。

我们将在后端添加几个类的实现，图12.1描述了将进一步开发的主类之间的高层关系:

\myGraphic{1.0}{content/part4/chapter12/images/1.png}{图12.1 - 主类之间的关系}

\mySubsubsection{12.2.1.}{简化DAG——处理合法类型和设置操作}

首先，实现M88kISelLowering，该类存储在M88kISelLowering.cpp文件中。构造函数配置合法的类型和操作:

\begin{enumerate}
\item
构造函数将对TargetMachine和M88kSubtarget类的引用作为参数。TargetMachine类负责目标的一般配置，需要运行。LLVM后端通常针对一个CPU系列，M88kSubtarget类描述所选CPU的特性。我们将在本章后面讨论这两个类:

\begin{cpp}
M88kTargetLowering::M88kTargetLowering(
    const TargetMachine &TM, const M88kSubtarget &STI)
    : TargetLowering(TM), Subtarget(STI) {
\end{cpp}

\item
第一个动作是声明哪个机器值类型使用哪个寄存器类，寄存器类从目标描述中生成。这里，只处理32位的值:

\begin{cpp}
    addRegisterClass(MVT::i32, &M88k::GPRRegClass);
\end{cpp}

\item
添加了所有的寄存器类之后，必须计算这些寄存器类的派生属性。需要查询子目标以获取寄存器信息，这些信息大多由目标描述生成:

\begin{cpp}
computeRegisterProperties(Subtarget.getRegisterInfo());
\end{cpp}

\item
接下来，必须声明哪个寄存器包含堆栈指针:

\begin{cpp}
setStackPointerRegisterToSaveRestore(M88k::R31);
\end{cpp}

\item
布尔值在不同平台上的表示方式不同。对于我们的目标，声明一个布尔值存储在0位，其他位将清除:

\begin{cpp}
setBooleanContents(ZeroOrOneBooleanContent);
\end{cpp}

\item
之后，设置函数的对齐方式。最小函数对齐是正确执行所需的对齐，给出了首选的对齐方式:

\begin{cpp}
setMinFunctionAlignment(Align(4));
setPrefFunctionAlignment(Align(4));
\end{cpp}

\item
最后，声明哪些操作是合法的。前一章中，只定义了三个逻辑指令，对32位值是合法的:

\begin{cpp}
setOperationAction(ISD::AND, MVT::i32, Legal);
setOperationAction(ISD::OR, MVT::i32, Legal);
setOperationAction(ISD::XOR, MVT::i32, Legal);
\end{cpp}

\item
除了Legal之外，还可以使用其他几个动作。Promote扩大类型，Expand用其他操作替换操作，LibCall将操作降低为库调用，而Custom调用LowerOperation()钩子方法，就可以实现自定义处理。例如，在M88k架构中，没有计数指令，因此要求将此操作扩展为其他操作:

\begin{cpp}
    setOperationAction(ISD::CTPOP, MVT::i32, Expand);
}
\end{cpp}
\end{enumerate}

现在，在M88kInstrInfo.td文件中提到的目标描述中，我们用and助记符定义了一条机器指令，并为其添加了一个模式。人若扩展AND多类记录，并且只查看使用三个寄存器的指令，可以得到TableGen的定义:

\begin{cpp}
let isCommutable = 1 in
    def ANDrr : F_LR<0b01000, Func, /*comp=*/0b0, "and",
                    [(set i32:$rd,
                        (and GPROpnd:$rs1, GPROpnd:$rs2))]>;
\end{cpp}

“and”字符串是指令的助记符。C++源代码中，使用M88k::ANDrr来引用这个指令。模式内部，使用DAG和节点类型。C++中，会命名为ISD::AND，在setOperationAction()方法中使用。指令选择期间，若模式匹配，则和类型的DAG节点可使用M88k::ANDrr指令替换，其中包括输入操作数。进行指令选择时，最重要的任务是定义正确的合法化行为，并将模式附加到指令定义中。

\mySubsubsection{12.2.2.}{向下转译DAG——处理形参}

转到M88kISelLowering类执行的另一个重要任务。我们在前一节中定义了调用约定的规则，但是还需要将物理寄存器和内存位置映射到DAG中使用的虚拟寄存器。对于参数，这在LowerFormalArguments()方法中完成，返回值在LowerReturn()方法中处理。首先，我们必须处理实参:

\begin{enumerate}
\item
将从包含生成的源代码开始:

\begin{cpp}
#include "M88kGenCallingConv.inc"
\end{cpp}

\item
LowerFormalArguments()方法接受几个参数。SDValue类表示与DAG节点关联的值，处理DAG时经常使用。第一个参数Chain表示控制流，可能更新的Chain也是该方法的返回值。CallConv参数标识所使用的调用约定，若变量参数列表是参数的一部分，则IsVarArg设置为true。需要处理的参数在Ins参数中传递，以及在DL参数中的位置，DAG参数能够访问SelectionDAG类。最后，映射的结果将存储在InVals vector参数中:

\begin{cpp}
SDValue M88kTargetLowering::LowerFormalArguments(
    SDValue Chain, CallingConv::ID CallConv,
    bool IsVarArg,
    const SmallVectorImpl<ISD::InputArg> &Ins,
    const SDLoc &DL, SelectionDAG &DAG,
    SmallVectorImpl<SDValue> &InVals) const {
\end{cpp}

\item
我们的第一个动作是检索对machine函数和machine寄存器信息的引用:

\begin{cpp}
    MachineFunction &MF = DAG.getMachineFunction();
    MachineRegisterInfo &MRI = MF.getRegInfo();
\end{cpp}

\item
接下来，必须调用生成的代码。需要实例化CCState类的对象，对AnalyzeFormalArguments()方法的调用中，使用的CC\_M88k参数值是在目标描述中使用的约定名称。结果存储在arglos vector中:

\begin{cpp}
    SmallVector<CCValAssign, 16> ArgLocs;
    CCState CCInfo(CallConv, IsVarArg, MF, ArgLocs,
        *DAG.getContext());
    CCInfo.AnalyzeFormalArguments(Ins, CC_M88k);
\end{cpp}

\item
当确定了参数的位置，需要将它们映射到DAG，必须遍历所有位置:

\begin{cpp}
    for (unsigned I = 0, E = ArgLocs.size(); I != E; ++I) {
        SDValue ArgValue;
        CCValAssign &VA = ArgLocs[I];
        EVT LocVT = VA.getLocVT();
\end{cpp}

\item
映射取决于确定的位置，处理分配给寄存器的参数。目标是将物理寄存器复制到虚拟寄存器，需要确定正确的寄存器类。因为只处理32位的值，所以这样做很容易:

\begin{cpp}
        if (VA.isRegLoc()) {
            const TargetRegisterClass *RC;
            switch (LocVT.getSimpleVT().SimpleTy) {
            default:
                llvm_unreachable("Unexpected argument type");
            case MVT::i32:
                RC = &M88k::GPRRegClass;
                break;
            }
\end{cpp}

\item
使用存储在RC变量中的寄存器类，可以创建虚拟寄存器并复制值。还需要将物理寄存器声明为“常驻”(live-in):

\begin{cpp}
            Register VReg = MRI.createVirtualRegister(RC);
            MRI.addLiveIn(VA.getLocReg(), VReg);
            ArgValue =
                DAG.getCopyFromReg(Chain, DL, VReg, LocVT);
\end{cpp}

\item
调用约定的定义中，增加了8位和16位值提升为32位的规则，需要确保这里的提升。必须插入DAG节点，以确保提升该值，该值会截断为正确的大小。注意，将ArgValue的值作为操作数传递给DAG节点，并将结果存储在同一个变量中:

\begin{cpp}
            if (VA.getLocInfo() == CCValAssign::SExt)
                ArgValue = DAG.getNode(
                    ISD::AssertSext, DL, LocVT, ArgValue,
                    DAG.getValueType(VA.getValVT()));
            else if (VA.getLocInfo() == CCValAssign::ZExt)
                ArgValue = DAG.getNode(
                    ISD::AssertZext, DL, LocVT, ArgValue,
                    DAG.getValueType(VA.getValVT()));
            if (VA.getLocInfo() != CCValAssign::Full)
                ArgValue = DAG.getNode(ISD::TRUNCATE, DL,
                                        VA.getValVT(), ArgValue);
\end{cpp}

\item
最后，通过将DAG节点添加到结果vector来完成对寄存器参数的处理:

\begin{cpp}
            InVals.push_back(ArgValue);
        }
\end{cpp}

\item
参数的另一个可能位置是在堆栈上，但没有定义加载和存储指令，还不能处理这种情况。这将结束所有参数位置的循环:

\begin{cpp}
        } else {
            llvm_unreachable("Not implemented");
        }
    }
\end{cpp}

\item
之后，可能需要添加代码来处理变量参数列表。再一次，添加了一些代码，来提醒我们没有实现它:

\begin{cpp}
    assert(!IsVarArg && "Not implemented");
\end{cpp}

\item
最后，必须返回Chain参数:

\begin{cpp}
    return Chain;
}
\end{cpp}
\end{enumerate}

\mySubsubsection{12.2.3.}{向下转译DAG——处理返回值}

返回值的处理方式类似，但必须扩展目标描述。首先，需要定义一个名为RET\_GLUE的新DAG节点类型。这种DAG节点类型用于将返回值粘合在一起，从而防止重新排列，例如由指令调度程序重新排列。M88kInstrInfo.td中的定义如下所示:

\begin{cpp}
def retglue : SDNode<"M88kISD::RET_GLUE", SDTNone,
                [SDNPHasChain, SDNPOptInGlue, SDNPVariadic]>;
\end{cpp}

同一个文件中，还定义了一个伪指令来表示函数调用的返回，将用于RET\_GLUE节点:

\begin{cpp}
let isReturn = 1, isTerminator = 1, isBarrier = 1,
        AsmString = "RET" in
    def RET : Pseudo<(outs), (ins), [(retglue)]>;
\end{cpp}

我们将在生成输出时展开这个伪指令。

有了这些定义，就可以实现LowerReturn()方法了:

\begin{enumerate}
\item
参数与LowerFormalArguments()相同，只是顺序略有不同:

\begin{cpp}
SDValue M88kTargetLowering::LowerReturn(
    SDValue Chain, CallingConv::ID CallConv,
    bool IsVarArg,
    const SmallVectorImpl<ISD::OutputArg> &Outs,
    const SmallVectorImpl<SDValue> &OutVals,
    const SDLoc &DL, SelectionDAG &DAG) const {
\end{cpp}

\item
首先，调用生成的代码，这次使用RetCC\_M88k的调用约定:

\begin{cpp}
    SmallVector<CCValAssign, 16> RetLocs;
    CCState RetCCInfo(CallConv, IsVarArg,
                        DAG.getMachineFunction(), RetLocs,
                        *DAG.getContext());
    RetCCInfo.AnalyzeReturn(Outs, RetCC_M88k);
\end{cpp}

\item
然后，再次遍历这些位置。根据当前调用约定的简单定义，该循环最多执行一次。若增加对返回64位值的支持，这将会改变，这需要在两个寄存器中返回:

\begin{cpp}
    SDValue Glue;
    SmallVector<SDValue, 4> RetOps(1, Chain);
    for (unsigned I = 0, E = RetLocs.size(); I != E; ++I) {
        CCValAssign &VA = RetLocs[I];
\end{cpp}

\item
之后，将返回值复制到分配给返回值的物理寄存器中。这与处理参数非常相似，除了使用Glue变量将值粘合在一起:

\begin{cpp}
    Register Reg = VA.getLocReg();
    Chain = DAG.getCopyToReg(Chain, DL, Reg, OutVals[I], Glue);
    Glue = Chain.getValue(1);
    RetOps.push_back(
        DAG.getRegister(Reg, VA.getLocVT()));
}
\end{cpp}

\item
返回值是链和胶合寄存器的复制操作，后者只有在有值返回时才会返回:

\begin{cpp}
    RetOps[0] = Chain;
    if (Glue.getNode())
        RetOps.push_back(Glue);
\end{cpp}

\item
最后，构造一个RET\_GLUE类型的DAG节点，传递必要的值:

\begin{cpp}
    return DAG.getNode(M88kISD::RET_GLUE, DL, MVT::Other,
                        RetOps);
}
\end{cpp}
\end{enumerate}

恭喜!有了这些定义，就为指令选择奠定了基础。

\mySubsubsection{12.2.4.}{指令选择中实现DAG到DAG的转换}

目前，仍然缺少一个关键部分:需要定义执行目标描述中定义的DAG转换的传递。该类名为M88kDAGToDAGISel，存储在M88kISelDAGToDAG.cpp文件中。类的大部分都生成了，但仍然需要添加一些代码:

\begin{enumerate}
\item
我们将首先定义调试类型并为该传递提供描述性名称:

\begin{cpp}
#define DEBUG_TYPE "m88k-isel"
#define PASS_NAME
            "M88k DAG->DAG Pattern Instruction Selection"
\end{cpp}

\item
然后，必须在匿名命名空间中声明该类。只重写Select()方法，其他代码会生成并包含在类的主体中:

\begin{cpp}
class M88kDAGToDAGISel : public SelectionDAGISel {
public:
    static char ID;

    M88kDAGToDAGISel(M88kTargetMachine &TM,
                     CodeGenOpt::Level OptLevel)
        : SelectionDAGISel(ID, TM, OptLevel) {}

    void Select(SDNode *Node) override;

#include "M88kGenDAGISel.inc"
};
} // end anonymous namespace
\end{cpp}

\item
之后，必须添加初始化传递的代码。LLVM后端仍然使用遗留的通道管理器，其设置与用于IR转换的通道管理器不同，静态成员ID值用于标识通道。初始化通道可以使用INITIALIZE\_PASS宏来实现，该宏扩展为C++代码。还必须添加一个工厂方法来创建实例:

\begin{cpp}
char M88kDAGToDAGISel::ID = 0;

INITIALIZE_PASS(M88kDAGToDAGISel, DEBUG_TYPE, PASS_NAME,
                false, false)

FunctionPass *
llvm::createM88kISelDag(M88kTargetMachine &TM,
                        CodeGenOpt::Level OptLevel) {
    return new M88kDAGToDAGISel(TM, OptLevel);
}
\end{cpp}

\item
最后，必须实现Select()方法。只调用生成的代码，但遇到了一个复杂的转换，就不能用DAG模式来表达，则可以在调用生成的代码之前，添加自己的代码来执行转换:

\begin{cpp}
void M88kDAGToDAGISel::Select(SDNode *Node) {
    SelectCode(Node);
}
\end{cpp}
\end{enumerate}

这样，就实现了指令选择。进行第一次测试之前，仍然需要添加一些支持类。我们将在接下来的几节中研究这些类。
















